HyperLib 1997 Winter - Disc 1/HYPERLIB-1997-Winter-CD1.ISO.7z/HYPERLIB-1997-Winter-CD1.ISO/オンラインウェア/UTIL/PL 2.0 SupplementDoc Folder.sit/PL 2.0 SupplementDoc Folder/Documentation/Chapter 20. The Evaluator

Text File | 1995-03-28 | 14KB | 333 lines

Common Lisp the Language, 2nd Edition
-------------------------------------------------------------------------------

20. The Evaluator

The mechanism that executes Lisp programs is called the evaluator. More
precisely, the evaluator accepts a form and performs the computation specified
by the form. This mechanism is made available to the user through the function
eval.

The evaluator is typically implemented as an interpreter that traverses the
given form recursively, performing each step of the computation as it goes. An
interpretive implementation is not required, however. A permissible alternative
approach is for the evaluator first to completely compile the form into
machine-executable code and then invoke the resulting code. This technique
virtually eliminates incompatibilities between interpreted and compiled code
but also renders the evalhook mechanism relatively useless. Various mixed
strategies are also possible. All of these approaches should produce the same
results when executing a correct program but may produce different results for
incorrect programs. For example, the approaches may differ as to when macro
calls are expanded; macro definitions should not depend on the time at which
they are expanded. Implementors should document the evaluation strategy for
each implementation.

-------------------------------------------------------------------------------

   *  Run-Time Evaluation of Forms
   *  The Top-Level Loop

-------------------------------------------------------------------------------

20.1. Run-Time Evaluation of Forms

The function eval is the main user interface to the evaluator. Hooks are
provided for user-supplied debugging routines to obtain control during the
execution of an interpretive evaluator. The functions evalhook and applyhook
provide alternative interfaces to the evaluator mechanism for use by these
debugging routines.

[Function]
eval form

The form is evaluated in the current dynamic environment and a null lexical
environment. Whatever results from the evaluation is returned from the call to
eval.

Note that when you write a call to eval two levels of evaluation occur on the
argument form you write. First the argument form is evaluated, as for arguments
to any function, by the usual argument evaluation mechanism (which involves an
implicit use of eval). Then the argument is passed to the eval function, where
another evaluation occurs. For example:

(eval (list 'cdr (car '((quote (a . b)) c)))) => b

The argument form (list 'cdr (car '((quote (a . b)) c))) is evaluated in the
usual way to produce the argument (cdr (quote (a . b))); this is then given to
eval because eval is being called explicitly, and eval evaluates its argument
(cdr (quote (a . b))) to produce b.

If all that is required for some application is to obtain the current dynamic
value of a given symbol, the function symbol-value may be more efficient than
eval.

[change_begin]
X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
user side effects; see section 7.9.
[change_end]

[Variable]
*evalhook*
*applyhook*

If the value of *evalhook* is not nil, then eval behaves in a special way. The
non-nil value of *evalhook* should be a function that takes two arguments, a
form and an environment; this is called the eval hook function. When a form is
to be evaluated (any form at all, even a number or a symbol), whether
implicitly or via an explicit call to eval, no attempt is made to evaluate the
form. Instead, the hook function is invoked and is passed the form to be
evaluated as its first argument. The hook function is then responsible for
evaluating the form; whatever is returned by the hook function is assumed to be
the result of evaluating the form.

The variable *applyhook* is similar to *evalhook* but is used when a function
is about to be applied to arguments. If the value of *applyhook* is not nil,
then eval behaves in a special way.

[old_change_begin]
The non-nil value of *applyhook* should be a function that takes three
arguments: a function, a list of arguments, and an environment; this is called
the apply hook function.
[old_change_end]

[change_begin]
X3J13 voted in January 1989 (APPLYHOOK-ENVIROMENT)   to revise the definition
of *applyhook*. Its value should be a function of two arguments, a function and
a list of arguments; no environment information is passed to an apply hook
function.
[change_end]

This was simply a flaw in the first edition. Sorry about that.

When a function is about to be applied to a list of arguments, no attempt is
made to apply the function. Instead, the hook function is invoked and is passed
the function and the list of arguments as its first and second arguments. The
hook function is then responsible for evaluating the form; whatever is returned
by the hook function is assumed to be the result of evaluating the form. The
apply hook function is used only for application of ordinary functions within
eval. It is not used for applications via apply or funcall, for applications by
such functions as map or reduce, or for invocation of macro-expansion functions
by either eval or macroexpand.

[change_begin]
X3J13 voted in June 1988 (FUNCTION-TYPE)   to specify that the value of
*macroexpand-hook* is first coerced to a function before being called as the
expansion interface hook. This vote made no mention of *evalhook* or
*applyhook*, but this may have been an oversight.

A proposal was submitted to X3J13 in September 1989 to specify that the value
of *evalhook* or *applyhook* is first coerced to a function before being
called. If this proposal is accepted, the value of either variable may be nil,
any other symbol, a lambda-expression, or any object of type function.
[change_end]

The last argument passed to either kind of hook function contains information
about the lexical environment in an implementation-dependent format. These
arguments are suitable for the functions evalhook, applyhook, and macroexpand.

When either kind of hook function is invoked, both of the variables *evalhook*
and *applyhook* are rebound to the value nil around the invocation of the hook
function. This is so that the hook function will not be invoked recursively on
evaluations and applications that occur in the course of executing the code of
the hook function. The functions evalhook and applyhook are useful for
performing recursive evaluations and applications within the hook function.

The hook feature is provided as an aid to debugging. The step facility is
implemented using this hook.

If a non-local exit causes a throw back to the top level of Lisp, perhaps
because an error could not be corrected, then *evalhook* and *applyhook* are
automatically reset to nil as a safety feature.

[Function]

evalhook form evalhookfn applyhookfn &optional env
applyhook function args evalhookfn applyhookfn &optional env

The functions evalhook and applyhook are provided to make it easier to exploit
the hook feature.

In the case of evalhook, the form is evaluated. In the case of applyhook, the
function is applied to the list of arguments args. In either case, for the
duration of the operation the variable *evalhook* is bound to evalhookfn, and
*applyhook* is bound to applyhookfn. Furthermore, the env argument is used as
the lexical environment for the operation; env defaults to the null
environment. The check for a hook function is bypassed for the evaluation of
the form itself (for evalhook) or for the application of the function to the
args itself (for applyhook), but not for subsidiary evaluations and
applications such as evaluations of subforms. It is this one-shot bypass that
makes evalhook and applyhook so useful.

[change_begin]
X3J13 voted in January 1989 (APPLYHOOK-ENVIROMENT)   to eliminate the optional
env parameter to applyhook, because it is not (and cannot) be useful. Any
function that can be applied carries its own environment and does not need
another environment to be specified separately. This was a flaw in the first
edition.
[change_end]

Here is an example of a very simple tracing routine that uses just the evalhook
feature.

(defvar *hooklevel* 0)

(defun hook (x)
  (let ((*evalhook* 'eval-hook-function))
    (eval x)))

(defun eval-hook-function (form &rest env)
  (let ((*hooklevel* (+ *hooklevel* 1)))
    (format *trace-output* "~%~V@TForm:  ~S"
            (* *hooklevel* 2) form)
    (let ((values (multiple-value-list
                     (evalhook form
                               #'eval-hook-function
                               nil
                               env))))
      (format *trace-output* "~%~V@TValue:~{ ~S~}"
              (* *hooklevel* 2) values)
      (values-list values))))

Using these routines, one might see the following interaction:

(hook '(cons (floor *print-base* 2) 'b))
  Form:  (CONS (FLOOR *PRINT-BASE* 2) (QUOTE B))
    Form:  (FLOOR *PRINT-BASE* 3)
      Form:  *PRINT-BASE*
      Value: 10
      Form:  3
      Value: 3
    Value: 3 1
    Form:  (QUOTE B)
    Value: B
  Value: (3 . B)
(3 . B)

[Function]
constantp object

If the predicate constantp is true of an object, then that object, when
considered as a form to be evaluated, always evaluates to the same thing; it is
a constant. This includes self-evaluating objects such as numbers, characters,
strings, bit-vectors, and keywords, as well as all constant symbols declared by
defconstant, such as nil, t, and pi. In addition, a list whose car is quote,
such as (quote foo), is considered to be a constant.

If constantp is false of an object, then that object, considered as a form,
might or might not always evaluate to the same thing.

-------------------------------------------------------------------------------

20.2. The Top-Level Loop

Normally one interacts with Lisp through a ``top-level read-eval-print loop,''
so called because it is the highest level of control and consists of an endless
loop that reads an expression, evaluates it, and prints the results. One has an
effect on the state of the Lisp system only by invoking actions that have side
effects.

The precise nature of the top-level loop for Common Lisp is purposely not
rigorously specified here so that implementors can experiment to improve the
user interface. For example, an implementor may choose to require
line-at-a-time input, or may provide a fancy editor or complex graphics-display
interface. An implementor may choose to provide explicit prompts for input, or
may choose (as MacLisp does) not to clutter up the transcript with prompts.

The top-level loop is required to trap all throws and recover gracefully. It is
also required to print all values resulting from evaluation of a form, perhaps
on separate lines. If a form returns zero values, as little as possible should
be printed.

The following variables are maintained by the top-level loop as a limited
safety net, in case the user forgets to save an interesting input expression or
output value. (Note that the names of some of these variables violate the
convention that names of global variables begin and end with an asterisk.)
These are intended primarily for user interaction, which is why they have short
names. Use of these variables should be avoided in programs.

[Variable]

++
+++

While a form is being evaluated by the top-level loop, the variable + is bound
to the previous form read by the loop. The variable ++ holds the previous value
of + (that is, the form evaluated two interactions ago), and +++ holds the
previous value of ++.

[Variable]


While a form is being evaluated by the top-level loop, the variable - is bound
to the form itself; that is, it is the value about to be given to + once this
interaction is done.

[change_begin]
Notice of correction. In the first edition, the name of the variable - was
inadvertently omitted.
[change_end]

[Variable]

**
***

While a form is being evaluated by the top-level loop, the variable * is bound
to the result printed at the end of the last time through the loop; that is, it
is the value produced by evaluating the form in +. If several values were
produced, * contains the first value only; * contains nil if zero values were
produced. The variable ** holds the previous value of * (that is, the result
printed two interactions ago), and *** holds the previous value of **.

If the evaluation of + is aborted for some reason, then the values associated
with *, **, and *** are not updated; they are updated only if the printing of
values is at least begun (though not necessarily completed).

[Variable]

//
///

While a form is being evaluated by the top-level loop, the variable / is bound
to a list of the results printed at the end of the last time through the loop;
that is, it is a list of all values produced by evaluating the form in +. The
value of * should always be the same as the car of the value of /. The variable
// holds the previous value of / (that is, the results printed two interactions
ago), and /// holds the previous value of //. Therefore the value of ** should
always be the same as the car of //, and similarly for *** and ///.

If the evaluation of + is aborted for some reason, then the values associated
with /, //, and /// are not updated; they are updated only if the printing of
values is at least begun (though not necessarily completed).

As an example of the processing of these variables, consider the following
possible transcript, where > is a prompt by the top-level loop for user input:

>(cons - -)             ;Interaction 1
((CONS - -) CONS - -)   ;Cute, huh?

>(values)               ;Interaction 2
                        ;Nothing to print

>(cons 'a 'b)   ;Interaction 3
(A . B)                 ;There is a single value

>(hairy-loop)^G ;Interaction 4
### QUIT to top level.  ;(User aborts the computation.)

>(floor 13 4)   ;Interaction 5
3                       ;There are two values


At this point we have:

+++ => (cons 'a 'b)   *** => NIL      /// => ()
++ => (hairy-loop)    ** => (A . B)   // => ((A . B))
+ => (floor 13 4)     * => 3          / => (3 1)

-------------------------------------------------------------------------------